1. Field of the Invention
The present invention relates to a Huffman code decoding circuit for decoding a huffman code. More specifically, the invention relates to a Huffman code decoding circuit to be used for data compression in an image compression processing system or so forth and is capable of realizing improvement for decoding process speed and integration.
2. Description of the Related Art
Conventional huffman code decoding circuit employs a memory having an address for a maximum code address or a circuit for tracking a decoding tree for each bit in order to attribute a decoded word corresponding to the Huffman code.
FIG. 11 is a block diagram showing another conventional Huffman code. As shown in FIG. 11, the decoding circuit performs decoding process by tracking a decoding tree for each bit. The decoding circuit has a latch 210 and an internal memory 211. The internal memory 211 is of construction of 512 W.times.9 bits. In the internal memory 211, a leading one bit of a Huffman code data sequence is input as a least significant address, and 8 bits of an output of the latch circuit 210 is also input as upper 8 bits of the address.
On the other hand, the latch circuit 210 latches a pointer when the pointer is output from the internal memory 211. Among 9 bits of the output of the internal memory 211, 8 bit expresses a decoded word or the pointer, and remaining one bit is "1" if the output is the decoded word and "0" if the output is the pointer.
In the operation of the decoding circuit set forth above, at first, a memory address is determined based on 1 bit input from the Huffman code data sequence to obtain the output of the internal memory 211. When the output result is the pointer, the internal memory 211 is again accessed based on the pointer and the next 1 bit of the Huffman code data sequence. When the output is the decoded word, one cycle of decoding process is finished.
Such circuit to perform decoding by tracking the decoding tree for each bit, memory access for the times corresponding to number of code bits to lower decoding process speed.
A further example of the Huffman code decoding circuit, in which the decoding process speed is improved, is illustrated in FIG. 12. As shown in FIG. 12, the shown Huffman code decoding circuit has a memory 219 having address with a length corresponding to the maximum code length. This memory 219 has a construction of 64 kW.times.13 bits. Namely, the Huffman code data sequence is input to an address input of the memory 219. Then, a decoded word and a code length are obtained as the output of the memory 219 corresponding to the address. Here, assuming that the maximum code length is 16 bits and the decoded word is 8 bits, the 8 bits of the decoded word and 5 bits code length. For instance, the decoded word for "all of addresses "01010 . . . 0".about."01011 . . . 1" A and the code length "4" are set. Similarly, for each address is set with respect to the Huffman code for each decoded word.
In the Huffman code decoding circuit, at first, 16 bits from the leading bit of the Huffman code data sequence is input to the address in the memory 219. Assuming that "0101 . . . " is transmitted, "0101 . . . ", "0101" is input to the 4 upper bits of the memory 219, and a Huffman code is input to the 12 lower bits. As set forth above, since the decoded word "A" and the code length "4" are set are set in respective addresses "01010 . . . 0".about."01011 . . . 1", the decoded word "A" and the code length "4" can be derived. With the code length "4", the leading bit of the Huffman code and 16 bits is determined and then the 16 bits are input to the address of the memory 219. In the similar manner, decoding process is repeated.
In such decoding circuit, the process speed may be improved. However, assuming that the maximum code length is 16 bits, it requires the memory size to be 65536 W. Therefore, when it is caused to causes increasing of the area and cost.
On the other hand, as a still further example of the conventional Huffman code decoding circuit, in which a method for providing a plurality of memory for accessing simultaneously and selecting the decoded word is employed. The construction of this type of the Huffman code decoding circuit is illustrated in FIG. 13. The shown decoding circuit includes a memory 301.about.309 taking the leading 15 bits so that 14th.about.8th bits, 13th.about.7th bits, 12th .about.6th bits, 11th.about.5th, 10th.about.4th bits, 9th.about.3rd bits, 8th.about.2nd bits, 7th.about.1st bits and 7th.about.0th being taken as address inputs relative to the 16 bits of 15th.about.0th bits. a selector 401, and a select signal generating circuit 402 for controlling the selector 401.
This circuit utilizes the fact that when number of word of the Huffman code is less than or equal to 256 words, and when "0" is present in the data sequence of the code, number of bits following the relevant bit is less than or equal to 7 bits.
At first, respective 8 bits decoded words and 4 bits code length are set in memories 301.about.309. The memory 301 is set the decoded word and the code length in the case of the decoded word representative of the Huffman code having "0" in the leading bit. For instance, if the Huffman code corresponding to the decoded word "A" is "0001", the decoded word "A" and the code length "4" are set for all of addresses "00100000".about."00111111" of the memory 301.
Similarly, the memory 302 is set the decoded word and the code length in the case of the decoded word representative of the Huffman code having "0" in the second leading bit. For instance, if the Huffman code corresponding to the decoded word "B" is "10011", the decoded word "B" and the code length "5" are set for all of addresses "01100000".about."01111111" of the memory 302. Subsequently, in the similar manner, when a pattern of the data sequence is a sequence, in which "0" is added for the trailing end of a sequence of "1" containing i (integer) -1 in number of "1", the decoded word and the code length are set in the first memory. On the other hand, all of the leading 8 bits are "1", i.e. "11111111", the decoded word and the code length are set for the memory 309.
The operation will be discussed hereinafter. Among 16 bits Huffman code data sequence, 7 bits from the 14th bit as the second leading bit to the 8th bits as the second leading bits are stored in the first memory 301, the 13th bits.about.6th bits as the leading third bits are stored in the memory 302. Subsequently, in the same manner, up to the seventh memory 308, 7 bits which is t-th bit from the leading bit is stored in t-1-th memory. Lower 8 bits, i.e. 7th.about.0th bits are stored in the memory 309. At the same time, 16 bits are supplied to a select signal generating portion 402.
Here, consideration is given for the case where the Huffman code data sequence "0001 . . . " is input. Then, "001" is input to the upper 3 bits of the address of the memory 301. Since the memory 301 is set the decoded word "A" and the code length "4" for all addresses of "00100000".about."00111111", the decoded word "A" and the code length "4" are output in response to the above-mentioned Huffman code. With respect to other memories 302.about.309, the decoded words and the code length corresponding to the above-mentioned address input are output. The outputs of these memories 301.about.309 are input to inputs 0.about.8 of the selector 401.
The select signal generating portion 402 feeds a select signal for selecting the output of the memory 301 to the selector 401 when the leading bit, i.e. 15th bit of the data sequence is "0". On the other hand, when the pattern of the data sequence is that "0" is added the trailing end of i-1 of series of "1", the select signal generating portion 403 feeds the select signal to the selector for selecting the first memory. For instance, when the above-mentioned pattern is "10", since i=2, the signal selecting the 2nd memory (i=2) 302 is fed. On the other hand, in case of the pattern having "1" in all bits, the signal selecting the 9th memory (i=9) 309 us fed to the selector.
The code length "4" of the 1st memory 301 output from the selector 401 us fed to the Huffman code data sequence. Thus, the leading end of the next Huffman code data sequence is determined. Subsequently, the decoding process is performed in the similar manner.
In case of the above-mentioned example, 128 words.times.12 bits.times.8 (memories 301.about.308)+256 words.times.12 bits.times.1 (memory 309)=1280 words.times.12 bits. In the decoding circuit constructed as set forth above, a plurality of memories are required to require greater chip area that a single memory of the same capacity, and expensive.